/*
 * main.cpp
 *
 *  Created on: 25.9.2011
 *      Author: duke
 */

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <stack>
#include <math.h>
#include "dynamic_array.h"
#include "graph.h"
#include "edge.h"
#include "stackitem.h"

using namespace std;

#define 	DEBUG 		0
#define 	TEST_DEPTH	2
#define 	TEST_EVERY	3

int numofruns = 0;
long maxruns = 0;
int test_depth = TEST_DEPTH;
int test_every = TEST_EVERY;
graph E1, E2;
graph A, B;
stack<stackitem> stack0;
void runRecursive(graph, int);
void runIterative(vector<edge> , bool, int, int);
/*
 *
 */
int main(int argc, char** argv) {
	ifstream myfile;
	string line;
	bool run_fast = false, run_recursive = false;
	int nodes, value, j = 0;
	for (int i = 1; i < argc; i++) {
		string parameter(argv[i]);
		if (parameter == "recursive")
			run_recursive = true;
		if (parameter == "fast") {
			run_fast = true;
#if DEBUG == 1
			cout << "branch and bound enabled..." << endl;
#endif
		}
		if (parameter == "-d") {
			i++;
			string parameter(argv[i]);
			test_depth = atoi(parameter.c_str());
		}

	}
	myfile.open(argv[1], ios::in);
	if (myfile.is_open()) {
		getline(myfile, line);
		istringstream is(line);
		if ((is >> nodes).fail()) {
#if DEBUG == 1
			cout << "error!" << endl;
#endif
			return -1;
		}
#if DEBUG == 1
		cout << "# of nodes: " << nodes << endl;
#endif
		dynamic_array input(nodes, nodes);
		while (myfile.good()) {
			getline(myfile, line);
			if ((int) line.length() == nodes) {
				for (int i = 0; i < (int) line.length(); i++) {
					value = line[i] - '0';
					input[i][j] = value;
				}
				j++;
			}
		}
		myfile.close();
		cout << "---------------------------" << endl;
		graph g1(input);
		maxruns = pow(2, g1.numOfEdges());
		cout << "max # of runs: " << maxruns << endl;
		g1.print();
		bool tfree = g1.isTriangleFree();
		if (tfree)
			cout << "triangle-free? yes" << endl;
		else
			cout << "triangle-free? no" << endl;
		if (run_recursive) {
			runRecursive(g1, 0);
		} else
			runIterative(g1.getAllEdges(), run_fast, test_depth, test_every);
		cout << endl << "BEST RESULTS: " << endl << "E1" << endl;
		E1.print();
		cout << "E2" << endl;
		E2.print();
		cout << "# of runs: " << numofruns << endl;
	} else {
		myfile.close();
	}
	return 0;
}

// rekurzivni zpusob reseni
void runRecursive(graph gr, int index) {
	vector<edge> temp = gr.getAllEdges();
	int size = temp.size();
	if (index == size) {
		numofruns++;
#if DEBUG == 1
		cout << "----------------------------------" << endl;
		for (vector<edge>::iterator it = temp.begin(); it != temp.end(); ++it) {
			it->print();
		}
#endif
		A.setEdges(gr.getEdges(0));
		B.setEdges(gr.getEdges(1));
#if DEBUG == 1
		A.print();
		B.print();
#endif
		if (A.numOfEdges() == B.numOfEdges() || A.numOfEdges()
				== B.numOfEdges() - 1) {
			if (A.numOfEdges() > E1.numOfEdges() && A.isTriangleFree()
					&& B.isTriangleFree()) {
				E1.setEdges(A.getAllEdges());
				E2.setEdges(B.getAllEdges());
			}
		}
		return;
	}
	gr.setEdgeColor(index, 0);
	runRecursive(gr, index + 1);
	gr.setEdgeColor(index, 1);
	runRecursive(gr, index + 1);
}

// iterativni zpusob reseni pomoci stacku
void runIterative(vector<edge> edges, bool fast, int _test_depth,
		int _test_every) {
	int index = 0;
	//int *array;
	stackitem si(0, edges);
	stack0.push(si);
	while (!stack0.empty()) {
		si = stack0.top();
		stack0.pop();
		index = si.getIndex();
		// posledni list
		if (index == (int) edges.size()) {
			numofruns++;
			//cout << "\rRunning... (index  " << numofruns << " out of "
			//		<< maxruns << ")";
			A.setEdges(si.getEdges(0));
			B.setEdges(si.getEdges(1));
			if (A.numOfEdges() == B.numOfEdges() || A.numOfEdges()
					== B.numOfEdges() - 1) {
				if (A.numOfEdges() > E1.numOfEdges() && A.isTriangleFree()
						&& B.isTriangleFree()) {
					// nalezeno lepsi reseni
					E1.setEdges(A.getAllEdges());
					E2.setEdges(B.getAllEdges());
					si.getArray();
					si.printArray();
				}
			}
#if DEBUG == 1
			si.print();
#endif
		} else {
			si.setIndex(index + 1);
			si.setEdgeColor(index, 0);
			if (fast && index > (int) edges.size() - ((int) edges.size()
					/ _test_depth) && index % _test_every == 0) {
				A.setEdges(si.getEdges(0));
				if (A.isTriangleFree())
					stack0.push(si);
			} else {
				stack0.push(si);
			}
			si.setEdgeColor(index, 1);
			if (fast && index > (int) edges.size() - ((int) edges.size()
					/ _test_depth) && index % _test_every == 0) {
				B.setEdges(si.getEdges(1));
				if (B.isTriangleFree())
					stack0.push(si);
			} else {
				stack0.push(si);
			}
		}
	}
}

